<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 6.0.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/wang-cheng/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/wang-cheng/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/wang-cheng/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/wang-cheng/images/logo.svg" color="#222">

<link rel="stylesheet" href="/wang-cheng/css/main.css">


<link rel="stylesheet" href="/wang-cheng/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"cheng-wang123.gitee.io","root":"/wang-cheng/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
  </script>

  <meta name="description" content="算法基础计数排序和基数排序 O(N)计数排序：对每一个输人元素x，确定小于x 的元素个数。 利用这一信息，就 可以直接把x放到它在输出数组中的位置上了。 例如，如果有17个元素小于x，则x就应该在第18个输出位置上。 当有几个元素相同时，这一方案要略做修改。 因为不能把它们放在同一个输出位置上。. 例如:对年龄进行统计，年龄一般是分布在0-200之间，申请一块200的数组，遍历需要排序的数组，将不">
<meta property="og:type" content="article">
<meta property="og:title" content="算法笔记(一)">
<meta property="og:url" content="https://cheng-wang123.gitee.io/wang-cheng/2022/03/31/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%80/index.html">
<meta property="og:site_name" content="诚の博客">
<meta property="og:description" content="算法基础计数排序和基数排序 O(N)计数排序：对每一个输人元素x，确定小于x 的元素个数。 利用这一信息，就 可以直接把x放到它在输出数组中的位置上了。 例如，如果有17个元素小于x，则x就应该在第18个输出位置上。 当有几个元素相同时，这一方案要略做修改。 因为不能把它们放在同一个输出位置上。. 例如:对年龄进行统计，年龄一般是分布在0-200之间，申请一块200的数组，遍历需要排序的数组，将不">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://cheng-wang123.gitee.io/wang-cheng/2022/03/31/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%80/%E6%AF%94%E8%BE%83%E5%99%A8.png">
<meta property="article:published_time" content="2022-03-31T02:24:12.000Z">
<meta property="article:modified_time" content="2022-04-06T09:10:42.515Z">
<meta property="article:author" content="王诚">
<meta property="article:tag" content="左神">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://cheng-wang123.gitee.io/wang-cheng/2022/03/31/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%80/%E6%AF%94%E8%BE%83%E5%99%A8.png">

<link rel="canonical" href="https://cheng-wang123.gitee.io/wang-cheng/2022/03/31/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%80/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>算法笔记(一) | 诚の博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/wang-cheng/atom.xml" title="诚の博客" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/wang-cheng/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">诚の博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">记录学习中的点点滴滴</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/wang-cheng/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/wang-cheng/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/wang-cheng/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/wang-cheng/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
  </ul>
</nav>




</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://cheng-wang123.gitee.io/wang-cheng/2022/03/31/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%80/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/wang-cheng/images/avatar.gif">
      <meta itemprop="name" content="王诚">
      <meta itemprop="description" content="命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="诚の博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          算法笔记(一)
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2022-03-31 10:24:12" itemprop="dateCreated datePublished" datetime="2022-03-31T10:24:12+08:00">2022-03-31</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2022-04-06 17:10:42" itemprop="dateModified" datetime="2022-04-06T17:10:42+08:00">2022-04-06</time>
              </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="算法基础"><a href="#算法基础" class="headerlink" title="算法基础"></a><strong>算法基础</strong></h1><h2 id="计数排序和基数排序-O-N"><a href="#计数排序和基数排序-O-N" class="headerlink" title="计数排序和基数排序 O(N)"></a><strong>计数排序和基数排序</strong> O(N)</h2><p>计数排序：对每一个输人元素x，确定小于x 的元素个数。 利用这一信息，就 可以直接把x放到它在输出数组中的位置上了。 例如，如果有17个元素小于x，则x就应该在第18个输出位置上。 当有几个元素相同时，这一方案要略做修改。 因为不能把它们放在同一个输出位置上。.</p>
<p>例如:对年龄进行统计，年龄一般是分布在0-200之间，申请一块200的数组，遍历需要排序的数组，将不同位置的数依次遍历，将遍历到的数与申请的数组的坐标进行对应并对其坐标位置上的数做++操作。遍历完成后，对申请的这个数组再进行遍历，遍历过程中对其进行排序。</p>
<p>基数排序：只对正整数有效，<strong>桶排序</strong></p>
<ol>
<li>先按个位数进行排序</li>
<li>在第一步的基础上，按十位数进行排序</li>
<li>在第二步的基础上，按百位数进行排序</li>
</ol>
<p>这样，最大值有多少位数，就执行多少轮。最重要的是：每一轮结束时，一定要更新列表，然后下一轮排序是在这个的基础上进行的</p>
<h2 id="基于比较的算法和不基于比较的算法"><a href="#基于比较的算法和不基于比较的算法" class="headerlink" title="基于比较的算法和不基于比较的算法"></a><strong>基于比较的算法和不基于比较的算法</strong></h2><p>只和两个数比大小有关的排序，是基于比较的排序算法，不是两个数比大小的排序，是不基于比较的排序</p>
<p>基于比较的算法有：选择、冒泡、插入、归并、快排、堆</p>
<p>时间复杂度分别为O(n^2)、O(n^2)、O(n^2)、O(n<em>logn)、O(n</em>logn)、O(n*logn)</p>
<p>空间复杂度分别为O(1)、O(1)、O(1)、O(N)、O(logn)、O(1)</p>
<p>稳定性分别为不稳定、稳定、稳定、稳定、不稳定、不稳定</p>
<p>不基于比较的排序：计数排序、基数排序等基于桶排序的算法都是不基于比较的排序</p>
<h2 id="排序算法中常见的坑"><a href="#排序算法中常见的坑" class="headerlink" title="排序算法中常见的坑"></a><strong>排序算法中常见的坑</strong></h2><ol>
<li><p>归并排序的额外空间复杂度可以变成0(1)，但是非常难，不需要掌握(因为既然需要将空间复杂度变为O(1)，直接用堆排序就OK了)，有兴趣可以搜”归并排序 内存缓存法”，但是变完之后不再稳定</p>
</li>
<li><p>“原地归并排序”的帖子更垃圾(因为这样会让时间复杂度变为O(N^2)，既然这样那直接用插入排序就OK了)</p>
</li>
<li><p>快速排序可以做到稳定性的问题，但是非常难，不需要掌握(因为这样会让空间复杂度变为O(N)，直接用归并就OK了)，可以搜”01 stable sort”</p>
</li>
<li><p>所有的改进都不重要，因为目前没找到时间复杂度O(N*logN)，额外空间复杂度O(1),又稳定的排序</p>
</li>
<li><p>有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官(经典的快排就是01标准，大于某个数的放左边，小于某个数的放右边，要么0要么1。这个题跟快排类似，奇数放左边，偶数放右边。但是，经典快排做不到稳定性)</p>
</li>
</ol>
<h2 id="算法汇总"><a href="#算法汇总" class="headerlink" title="算法汇总"></a><strong>算法汇总</strong></h2><p>稳定性：排完序之后，相同的元素之间的次序不变</p>
<p>例如：(class,age)这个表，先对age进行排序，排序后再对class进行排序，如果排序完后，每个class里的age都是从小到大(从大到小)，就说明这种第二次排序所用的排序算法是稳定的</p>
<p>具有稳定性的排序：冒泡、插入、归并、一切桶思想的排序</p>
<p>不具备稳定性的排序：选择排序、快速排序、堆排序</p>
<p>基于比较的排序，能不能做到时间复杂度在O(N*logN)以下——&gt;目前没找到</p>
<p>时间复杂度在O(N*logN)，并且空间复杂度在O(N)以下，还能做到稳定——&gt;目前没找到</p>
<h2 id="排序算法的选择"><a href="#排序算法的选择" class="headerlink" title="排序算法的选择"></a><strong>排序算法的选择</strong></h2><p>首先考虑快速排序，因为是最快速的排序。能用快排就用快排</p>
<p>如果实在是有空间的限制，很轻易就超出空间限制，则选择堆排序</p>
<p>如果需要做到稳定性，则可以选择归并排序</p>
<p>总结：</p>
<p>归并的劣势是空间复杂度较高，优势是稳定性能做到</p>
<p>快排的优势是它的常数项低，实际跑的时候是最快的排序。但劣势是空间复杂度没有办法做到O(1)，稳定性也无法做到</p>
<p>堆排的优势是它的空间使用很低，劣势是稳定性无法做到</p>
<h2 id="工程上对排序的一些改进"><a href="#工程上对排序的一些改进" class="headerlink" title="工程上对排序的一些改进"></a><strong>工程上对排序的一些改进</strong></h2><p>1) 充分利用O(N<em>logN)和O(N^2)排序<em>*各自</em></em>的优势</p>
<pre><code>+ 例如可以在快排分成两部分进行排序的时候，如果有一部分样本量比较小，可以直接用插入排序进行。叫做综合排序，也就是说在排序过程中又用了其他类型的排序。
</code></pre><p>2) 稳定性的考虑</p>
<h2 id="比较器的使用"><a href="#比较器的使用" class="headerlink" title="比较器的使用"></a><strong>比较器的使用</strong></h2><p>1) 比较器的实质是重载比较运算符</p>
<p>2) 比较器可以很好的应用在特殊标准的排序中</p>
<p>3) 比较器可以很好的应用在根据特殊标准排序的结构上</p>
<p>自定义比较器需要实现Comparator<Object>接口，实现里面的方法。</Object></p>
<img src="/wang-cheng/2022/03/31/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%B8%80/%E6%AF%94%E8%BE%83%E5%99%A8.png" class title="比较器">
<h2 id="链表"><a href="#链表" class="headerlink" title="链表"></a><strong>链表</strong></h2><h3 id="哈希表"><a href="#哈希表" class="headerlink" title="哈希表"></a><strong>哈希表</strong></h3><ol>
<li><p>哈希表在使用层面可以理解为一种集合结构</p>
</li>
<li><p>如果只有key，没有伴随数据value，可以使用HashSet结构</p>
</li>
<li><p>如果既有key又有value，可以使用HashMap</p>
</li>
<li><p>有无伴随数据，是HashMap和HashSet的唯一区别，底层的实际结构是一样的</p>
</li>
<li><p>使用哈希表增(put)、删(remove)、改(put)、查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大</p>
</li>
<li><p>放入哈希表中的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小</p>
</li>
<li><p>放入哈希表中的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小</p>
</li>
</ol>
<h3 id="有序表"><a href="#有序表" class="headerlink" title="有序表"></a><strong>有序表</strong></h3><ol>
<li><p>有序表在使用层面上可以理解为一种集合结构</p>
</li>
<li><p>如果只有key，没有伴随数据value,可以使用TreeSet结构</p>
</li>
<li><p>如果既有key又有value，可以使用TreeMap结构</p>
</li>
<li><p>有无伴随是TreeSet和TreeMap唯一的区别，底层实际结构是一样的</p>
</li>
<li><p>有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织</p>
</li>
<li><p>红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同</p>
</li>
<li><p>放入有序表中的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小</p>
</li>
<li><p>放入有序表中的东西，如果不是基础类型，内部提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小</p>
</li>
<li><p>不管是什么底层底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度</p>
<ul>
<li><p>void put(K key,V value)</p>
</li>
<li><p>V get(K key)</p>
</li>
<li><p>void remove(K key)</p>
</li>
<li><p>boolean containsKey(K key)</p>
</li>
<li><p>K firstKey()</p>
</li>
<li><p>K lastKey()</p>
</li>
<li><p>K floorKey(K key):如果表中存入过key，返回key，否则返回所有键值的排序结果中，key的前一个</p>
</li>
<li><p>K ceilingKey(K key):如果表中存入过key，返回key，否则返回所有键值的排序结果中，key的后一个</p>
</li>
</ul>
</li>
</ol>
<p>以上所有操作时间复杂度都是O(logN),N为有序表含有的记录数</p>
<h3 id="搜索二叉树的删除"><a href="#搜索二叉树的删除" class="headerlink" title="搜索二叉树的删除"></a><strong>搜索二叉树的删除</strong></h3><p>搜索二叉树的查找、添加都很好解决，但是删除的时候会遇到下面三种情况</p>
<p>要删除的节点是叶节点————直接删除</p>
<p>要删除的节点只有一个子节点————直接将该节点的父节点指向该节点的子节点</p>
<p>要删除的节点有两个子节点————拿左树最右侧节点替换(将左节点给这个节点的父节点)/拿右树最左测节点替换(将左节点给这个节点的父节点)</p>
<h3 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a><strong>红黑树</strong></h3><ol>
<li><p>每一个节点，不是红就是黑</p>
</li>
<li><p>红黑树中的叶节点，指的是最底层的空节点</p>
</li>
<li><p>根节点和叶节点都是黑</p>
</li>
<li><p>任何两个红节点不能相邻</p>
</li>
<li><p>从某一个头部cur出发到它叶节点的每一条路径，要求黑节点数量一样</p>
</li>
</ol>
<h3 id="链表解题的方法论"><a href="#链表解题的方法论" class="headerlink" title="链表解题的方法论"></a><strong>链表解题的方法论</strong></h3><ol>
<li><p>对于笔试，不用太在乎空间复杂度，一切为了时间复杂度</p>
</li>
<li><p>对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法</p>
</li>
</ol>
<p>也就是说链表的题在笔试的时候，空间复杂度不考虑，只要实现这个算法就OK，面试的时候，尽量不要使用额外变量，只用有限几个变量实现算法。</p>
<p>重要技巧：</p>
<ol>
<li><p>额外数据结构(哈希表等)</p>
</li>
<li><p>快慢指针(快指针走两步，慢指针走一步)</p>
</li>
</ol>
<hr>
<p><strong>接下来是利用有限变量来对解决链表问题</strong></p>
<p>单链表有环无环的判断:利用快慢指针</p>
<ul>
<li>如果指针在循环过程中指向null，则无环</li>
<li>如果快慢指针相遇，让快指针回到起始位置，然后变成慢指针继续循环，直到两个指针再次相遇，就是入环节点。</li>
</ul>
<hr>
<p>判断链表是否为回文链表：</p>
<p>笔试遇到，直接放入栈</p>
<p>面试遇到，用快慢指针</p>
<ol>
<li><p>快指针走两步，慢指针走一步，当快指针走到尾部，慢指针走到中间</p>
</li>
<li><p>从慢指针到尾部进行一个逆序，中间位置指向空。</p>
</li>
<li><p>用两个引用记住链表的头部和尾部，然后两个引用同时往中间走，直到走到中间，在这个过程中如果有一点不一样，则不是回文。</p>
</li>
<li><p>判断完成以后再把链表还原回去。</p>
</li>
</ol>
<hr>
<p>给定一个数将链表调整为左边小、中间相等、右边大的形式：</p>
<p>笔试遇到，将单链表每一个节点放到数组中，然后进行一次快排，然后再将数组串起来</p>
<p>面试遇到，使用6个变量就可以实现</p>
<ol>
<li><p>SH、ST、EH、ET、bH、bT，分别表示小于部分的头、小于部分的尾，等于部分的头、等于部分的尾、大于部分的头、大于部分的尾</p>
</li>
<li><p>遍历链表，对每一个节点</p>
<ul>
<li>如果小于给定的数，判断SH是否为空<ul>
<li>如果为空，则SH、ST都指向这个节点,</li>
<li>如果不为空，则ST.next = node; ST = node;</li>
</ul>
</li>
<li>如果大于给定的数，判断bH是否为空<ul>
<li>如果为空，则bH、bS都指向这个节点</li>
<li>如果不为空，则bT.next = node; bT = node;</li>
</ul>
</li>
<li>如果等于给定的数，与上面两者类似操作</li>
</ul>
</li>
<li>判断小于区域、大于区域、等于区域是否为null，不为null就给他们相连，为null则忽略调为null的区域，将不为null的区域想来你。相连原则为小于区域的尾部连等于区域的头部。等于区域的尾部连大于区域的头部</li>
</ol>
<p>复制含有随机指针节点的链表问题：</p>
<p>单链表中新增一个特殊指针，可能指向链表中任意一个节点，也可能指向null</p>
<p>笔试遇到：用哈希表Map<Node,Node>来做，遍历链表，Key存放老节点，value存放克隆出来的节点。遍历老链表，用遍历到的节点查出新链表，进行next指针和特殊指针的相连。</Node,Node></p>
<p>面试遇到：遍历链表，为每一个节点复制一个新的节点，并让节点指向新节点，然后新节点指向下一个节点。这样节点与新节点也会出现像Map结构中的对应关系。然后进行新链表的建立，最后将新链表从链表中分离出来。</p>
<p>判断两条链表相交问题:</p>
<ol>
<li><p>两条链表都无环，遍历两条链表找到两条链表的尾部，并记录下链表的长度len1、len2</p>
<ul>
<li>如果尾部不相等，则两条链表不相等</li>
<li>如果尾部相等,Math.abs(len1-len2),并让更长的链表的指针先走这个绝对值，然后两条链表共同往下遍历，当两条链表遍历到的值相等时，说明是相交点</li>
</ul>
</li>
<li><p>一条有环一条无环，则两条链表不可能相交</p>
</li>
<li><p>两条链表都有环，则有三种情况</p>
<ul>
<li>两条链表不相交<ul>
<li>根据情况1判断链表的尾部是否相等就可以判断</li>
</ul>
</li>
<li>相交处就是环的入口<ul>
<li>通过单链表有环无环的判断，可以找出两个链表的入环节点，如果两个链表的入环节点相同，则证明是这种情况。那么这个时候便可以看作是第一种情况下的第二种假设，即尾部相等，让更长的链表的指针先走一个绝对值，然后共同遍历找出相交点。</li>
</ul>
</li>
<li>在环上两个位置相交——在不同地点入环<ul>
<li>通过单链表有环无环的判断，可以找出两个链表的入环节点，如果两个链表的入环节点不相同，则证明是这种情况。那么这个时候其实可以直接返回任意一个链表的入环节点，因为这两个节点都是都是相交节点。</li>
</ul>
</li>
</ul>
</li>
</ol>
<h2 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a><strong>二叉树</strong></h2><h3 id="非递归遍历二叉树"><a href="#非递归遍历二叉树" class="headerlink" title="非递归遍历二叉树"></a><strong>非递归遍历二叉树</strong></h3><p>利用栈的性质</p>
<p>先序遍历</p>
<ol>
<li><p>将根节点放入栈中。然后弹出，打印(处理)该节点，然后先将右节点放入栈，再将左节点放入栈</p>
</li>
<li><p>从栈中弹出一个节点，打印(处理)该节点，然后先将右节点放入栈，再将左节点放入栈</p>
</li>
<li><p>重复第二步，如果左右节点都没有，则处理完节点后什么也不做。</p>
</li>
</ol>
<p>后序遍历</p>
<p>准备两个栈，一个收集栈，一个回收栈</p>
<ol>
<li><p>从根节点开始，放入收集栈</p>
</li>
<li><p>弹出收集栈中的一个，放入回收栈。再将这个节点的左节点、右节点分别放入收集栈</p>
</li>
<li><p>重复第二步</p>
</li>
</ol>
<p>中序遍历</p>
<p>每棵子树，整棵树左边界进栈，依次弹出的过程中，打印，然后对每个节点的右树，周而复始</p>
<h3 id="如何判断一棵二叉树是否是搜索二叉树"><a href="#如何判断一棵二叉树是否是搜索二叉树" class="headerlink" title="如何判断一棵二叉树是否是搜索二叉树"></a><strong>如何判断一棵二叉树是否是搜索二叉树</strong></h3><p>搜索二叉树的左树节点都比它小，右树都比它大</p>
<p>一棵搜索二叉树，用中序遍历是一定会升序排序的。</p>
<p>用中序遍历，如果发现它总是在升序，那么它肯定是搜索二叉树，如果某一个节点不是升序，那么就不是搜索二叉树。</p>
<ol>
<li><p>利用中序遍历递归，每次进入方法都先进行终止条件的判断(node == null)，达到终止条件则返回true</p>
</li>
<li><p>没有达到终止条件，则递归进入左节点。用一个值接收递归左节点返回来的值</p>
</li>
<li><p>如果返回true,则判断当前节点与左子节点的右子节点的值谁大，如果当前节点小于preValue(左孩子的右孩子的节点的值),返回false</p>
</li>
</ol>
<p>4.如果当前节点大于preValue(左孩子的右孩子的节点的值)，就将当前节点的值设置为preValue</p>
<ol>
<li>然后递归进当前节点的右子树查找，将递归的返回值作为返回值进行返回</li>
</ol>
<p><strong>用下面的套路解决</strong></p>
<p>当前节点为X</p>
<p>条件：</p>
<ol>
<li><p>左子树是搜索二叉树</p>
</li>
<li><p>右子树是搜索二叉树</p>
</li>
<li><p>左子树&lt;节点X</p>
</li>
<li><p>右子树&gt;节点X</p>
</li>
</ol>
<p>思考左右子树各需要给你什么信息</p>
<ol>
<li><p>左边是搜索二叉树，且给我最大值</p>
</li>
<li><p>右边是搜索二叉树，且给我最小值</p>
</li>
</ol>
<p>由于左子树要求跟右子树要求不一样，又因为递归要求的是返回是一样的，所以这里将他们统一一下，一律返回三个信息(是否是搜索二叉树，整棵树最小值是谁，整棵树最大值是谁)</p>
<hr>
<figure class="highlight processing"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">ReturnData</span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> isBST;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="built_in">min</span>;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> <span class="built_in">max</span>;</span><br><span class="line">    <span class="keyword">public</span> <span class="title function_">ReturnData</span>(<span class="type">boolean</span> is,<span class="type">int</span> mi,<span class="type">int</span> ma)&#123;</span><br><span class="line">        isBST = is;</span><br><span class="line">        <span class="built_in">min</span> = mi;</span><br><span class="line">        <span class="built_in">max</span> = ma;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> ReturnData <span class="title function_">process</span>(Node x)&#123;</span><br><span class="line">    <span class="keyword">if</span>(x == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    ReturnData leftData = <span class="title function_">process</span>(x.<span class="property">left</span>);</span><br><span class="line">    ReturnData rightData = <span class="title function_">process</span>(x.<span class="property">right</span>);</span><br><span class="line">    <span class="type">int</span> <span class="built_in">min</span> = x.<span class="property">value</span>;</span><br><span class="line">    <span class="type">int</span> <span class="built_in">max</span> = x.<span class="property">value</span>;</span><br><span class="line">    <span class="keyword">if</span>(leftData != <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="built_in">min</span> = Math.<span class="property">min</span>(<span class="built_in">min</span>,leftData.<span class="property">min</span>);</span><br><span class="line">        <span class="built_in">max</span> = Math.<span class="property">max</span>(<span class="built_in">max</span>,leftData.<span class="property">max</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(rightData != <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="built_in">min</span> = Math.<span class="property">min</span>(<span class="built_in">min</span>,rightData.<span class="property">min</span>);</span><br><span class="line">        <span class="built_in">max</span> = Math.<span class="property">max</span>(<span class="built_in">max</span>,rightData.<span class="property">max</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="type">boolean</span> BST = <span class="literal">true</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span>(leftData != <span class="literal">null</span> &amp;&amp; (!leftData.<span class="property">isBST</span> || leftData.<span class="property">max</span> &gt;= x.<span class="property">value</span>))&#123;</span><br><span class="line">        isBST = <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(leftData != <span class="literal">null</span> &amp;&amp; (!leftData.<span class="property">isBST</span> || x.<span class="property">value</span> &gt;= rightData.<span class="property">min</span> ))&#123;</span><br><span class="line">        isBST <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new </span><span class="class title_">ReturnData</span>(isBST,<span class="built_in">min</span>,<span class="built_in">max</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="如何判断一棵二叉树是完全二叉树"><a href="#如何判断一棵二叉树是完全二叉树" class="headerlink" title="如何判断一棵二叉树是完全二叉树"></a><strong>如何判断一棵二叉树是完全二叉树</strong></h3><ol>
<li><p>宽度优先遍历(队列)过程中，如果某一个节点有右节点没有左节点，直接返回false</p>
</li>
<li><p>在不违背1的条件下，如果遇到了第一个左右孩子不全的情况，那么接下来遇到的所有节点，都必须是叶节点。</p>
</li>
</ol>
<h3 id="如何判断一棵二叉树是否是满二叉树"><a href="#如何判断一棵二叉树是否是满二叉树" class="headerlink" title="如何判断一棵二叉树是否是满二叉树"></a><strong>如何判断一棵二叉树是否是满二叉树</strong></h3><p>用套路来解决：</p>
<p>封装数据</p>
<ol>
<li><p>整棵树的高度</p>
</li>
<li><p>树的节点个数</p>
</li>
</ol>
<figure class="highlight arduino"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="type">static</span> <span class="keyword">class</span> <span class="title class_">Info</span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> height;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> nodes;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">Info</span><span class="params">(<span class="type">int</span> h,<span class="type">int</span> n)</span></span>&#123;</span><br><span class="line">        height = h;</span><br><span class="line">        nodes = n;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="type">static</span> Info <span class="title">f</span><span class="params">(Node x)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(x == null)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="built_in">Info</span>(<span class="number">0</span>,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    Info leftData = <span class="built_in">f</span>(x.left);</span><br><span class="line">    Info rightData = <span class="built_in">f</span>(x.right);</span><br><span class="line">    <span class="type">int</span> height = Math.<span class="built_in">max</span>(leftData.height,rightData.height)+<span class="number">1</span>;</span><br><span class="line">    <span class="type">int</span> nodes = leftData.nodes + rightData.nodes + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="built_in">Info</span>(height,nodes);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="如何判断一棵二叉树是否是平衡二叉树-二叉树题目套路"><a href="#如何判断一棵二叉树是否是平衡二叉树-二叉树题目套路" class="headerlink" title="如何判断一棵二叉树是否是平衡二叉树(二叉树题目套路)"></a><strong>如何判断一棵二叉树是否是平衡二叉树(二叉树题目套路)</strong></h3><p>平衡二叉树：它左树的高度和它右树的高度的差都不超过1</p>
<p>如果以X为根节点进行判断</p>
<ol>
<li>X的左子树必须是平衡二叉树</li>
<li>X的右子树必须是平衡二叉树</li>
<li>两个子树的高度差不超过1</li>
</ol>
<p>思考左树和右树到底需要给你什么样的信息：</p>
<ol>
<li>是否是平的</li>
<li>高度是多少</li>
</ol>
<p>需要两个信息，则返回值需要俩值(用一个类封装两个信息)</p>
<ol>
<li><p>如果是空树，返回(是平衡二叉树，高度是0)这样的结构体</p>
</li>
<li><p>递归左子树和右子树。保存两个递归较大的那个高度+1</p>
</li>
<li><p>是否是平衡树由上面三个条件必须都成立才可以是平衡树。</p>
</li>
<li><p>返回(是否是平衡二叉树,高度是多少)</p>
<figure class="highlight arduino"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="type">static</span> <span class="type">boolean</span> <span class="title">isBalanced</span><span class="params">(Node head)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">process</span>(head).isBalanced;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="type">static</span> <span class="keyword">class</span> <span class="title class_">ReturnType</span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">boolean</span> isBalanced;</span><br><span class="line">    <span class="keyword">public</span> <span class="type">int</span> height;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">ReturnType</span><span class="params">(<span class="type">boolean</span> isB,<span class="type">int</span> hei)</span></span>&#123;</span><br><span class="line">        isBalanced = isB;</span><br><span class="line">        height = hei;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="type">static</span> ReturnType <span class="title">process</span><span class="params">(Node x)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(x == null)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="built_in">ReturnType</span>(<span class="literal">true</span>,<span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    ReturnType leftData = <span class="built_in">process</span>(x.left);</span><br><span class="line">    ReturnType rightData = <span class="built_in">process</span>(x.right);</span><br><span class="line">    <span class="type">int</span> height = Math.<span class="built_in">max</span>(leftData.height,rightData.height) + <span class="number">1</span>;</span><br><span class="line">    <span class="type">boolean</span> isBalanced = leftData.isBalanced &amp;&amp; rightData.isBalanced &amp;&amp; Math.<span class="built_in">abs</span>(leftData.height - rightData.height) &lt; <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="built_in">ReturnType</span>(isBalanced,height); </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br></pre></td></tr></table></figure>
</li>
</ol>
<p><strong>搜索二叉树、满二叉树、平衡二叉树都可以用这个套路</strong></p>
<p>这个套路其实就是一个树型Dp，树型Dp就是罗列所有的可能性。</p>
<p>这个套路就是动态规划，左子树给我的信息和右子树给我的信息就是他们动态规划出来的结果，我跟我他们给出的结果输出我的动态规划然后往上给。</p>
<p>只要我解决这个问题需要跟这棵树的左子树要信息并且需要跟我的右子树要信息，那么我就可以使用树型Dp。但并不是所有问题都可以用这个套路来解决。</p>
<h2 id="牛客NC102题目"><a href="#牛客NC102题目" class="headerlink" title="牛客NC102题目"></a><strong>牛客NC102题目</strong></h2><figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//o1 o2 一定属于head为头的树</span></span><br><span class="line"><span class="comment">//返回o1 o2的最低公共祖先</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">lca</span>(<span class="params">Node head,Node o1,Node o2</span>)</span>&#123;</span><br><span class="line">    HashMap&lt;Node,Node&gt; fatherMap = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    fatherMap.put(head,head);</span><br><span class="line">    process(head,fatherMap);</span><br><span class="line">    HashSet&lt;Node&gt; set1 = <span class="keyword">new</span> HashSet&lt;&gt;();</span><br><span class="line">    </span><br><span class="line">    Node cur = o1;</span><br><span class="line">    <span class="keyword">while</span>(cur != fatherMap.<span class="keyword">get</span>(cur))&#123;</span><br><span class="line">        set1.<span class="keyword">add</span>(cur);</span><br><span class="line">        cur = fatherMap.<span class="keyword">get</span>(cur);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    set1.<span class="keyword">add</span>(head);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">process</span>(<span class="params">Node head,HashMap&lt;Node,Node&gt; fatherMap</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(head == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    fatherMap.put(head.left,head);</span><br><span class="line">    fatherMap.put(head.right,head);</span><br><span class="line">    process(head.left,fatherMap);</span><br><span class="line">    process(head.right,fatherMap);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>更优解</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="type">int</span> <span class="title function_">lowestCommonAncestor</span> <span class="params">(TreeNode root, <span class="type">int</span> o1, <span class="type">int</span> o2)</span> &#123;</span><br><span class="line">    root = helper(root,o2,o1);</span><br><span class="line">    <span class="keyword">return</span> root.val;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">public</span> TreeNode <span class="title function_">helper</span><span class="params">(TreeNode root, <span class="type">int</span> o1,<span class="type">int</span> o2)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(root == <span class="literal">null</span> || root.val == o1 || root.val == o2)&#123;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;   </span><br><span class="line">    <span class="type">TreeNode</span> <span class="variable">node1</span> <span class="operator">=</span> helper(root.left,o1,o2);</span><br><span class="line">    <span class="type">TreeNode</span> <span class="variable">node2</span> <span class="operator">=</span> helper(root.right,o1,o2);</span><br><span class="line">    <span class="keyword">if</span>(node1 == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> node2;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(node2 == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> node1;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="在二叉树中找到一个节点的后继节点"><a href="#在二叉树中找到一个节点的后继节点" class="headerlink" title="在二叉树中找到一个节点的后继节点"></a><strong>在二叉树中找到一个节点的后继节点</strong></h2><p>后继节点:中序遍历中一个节点的后一个节点</p>
<p>前驱节点:中序遍历中一个节点的前一个节点</p>
<p>求X的的后继节点</p>
<ol>
<li>X有右树的时候，X的后继就是它右树上的最左节点</li>
<li>X无右树的时候，往上找，判断当前节点是否是父节点的左节点，如果是，则父节点是后继节点。</li>
</ol>
<figure class="highlight crmsh"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">public static <span class="keyword">Node</span> <span class="title">getSuccessorNode</span>(<span class="keyword">Node</span> <span class="title">node</span>)&#123;</span><br><span class="line">    if(<span class="keyword">node</span> <span class="title">== null</span>)&#123;</span><br><span class="line">        return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">    &#125;</span></span><br><span class="line"><span class="title">    if</span>(node.right != null)&#123;</span><br><span class="line">        return getLeftMost(node.right);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        //无右子树</span><br><span class="line">        <span class="keyword">Node</span> <span class="title">parent</span> = node.parent;</span><br><span class="line">        while(parent != null &amp;&amp; parent.left != <span class="keyword">node</span><span class="title">)&#123;</span></span><br><span class="line"><span class="title">            node</span> = parent;</span><br><span class="line">            parent = node.parent;</span><br><span class="line">        &#125;</span><br><span class="line">        return parent;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">public static <span class="keyword">Node</span> <span class="title">getLeftMost</span>(<span class="keyword">Node</span> <span class="title">node</span>)&#123;</span><br><span class="line">    if(<span class="keyword">node</span> <span class="title">== null</span>)&#123;</span><br><span class="line">        return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">    &#125;</span></span><br><span class="line"><span class="title"></span></span><br><span class="line"><span class="title">    while</span>(node.left != null)&#123;</span><br><span class="line">        <span class="keyword">node</span> <span class="title">= node</span>.left;</span><br><span class="line">    &#125;</span><br><span class="line">    return <span class="keyword">node</span><span class="title">;</span></span><br><span class="line"><span class="title">&#125;</span></span><br></pre></td></tr></table></figure>
<h2 id="字符串的序列化和反序列化"><a href="#字符串的序列化和反序列化" class="headerlink" title="字符串的序列化和反序列化"></a><strong>字符串的序列化和反序列化</strong></h2><p>序列化：对二叉树来说，就是内存里的二叉树，怎么给他变成硬盘里字符串的形式，而且这个字符串还要对应出唯一的结构。</p>
<p>也就是内存里的一棵树如何变成字符串的形式，又如何从字符串变成内存里的树</p>
<p>以什么样的方式序列化，就以什么样的方式反序列化</p>
<p>序列化的方式就是通过遍历子树，记录节点和为null的子节点。</p>
<p>如果通过先序遍历序列化二叉树，就要以先序遍历的方式反序列化回去。</p>
<p>序列化<br><figure class="highlight typescript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="title class_">String</span> <span class="title function_">serialByPre</span>(<span class="params">Node head</span>)&#123;</span><br><span class="line">    <span class="keyword">if</span>(head == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;#_&quot;</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="title class_">String</span> res = head.<span class="property">value</span> + <span class="string">&quot;_&quot;</span>;</span><br><span class="line">    res += <span class="title function_">serialByPre</span>(head.<span class="property">left</span>);</span><br><span class="line">    res += <span class="title function_">serialByPre</span>(head.<span class="property">right</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>反序列化<br><figure class="highlight arduino"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="type">static</span> Node <span class="title">reconByPreString</span><span class="params">(<span class="type">String</span> preStr)</span></span>&#123;</span><br><span class="line">    <span class="type">String</span>[] values = preStr.<span class="built_in">split</span>(<span class="string">&quot;_&quot;</span>);</span><br><span class="line">    Queue&lt;<span class="type">String</span>&gt; queue = <span class="keyword">new</span> <span class="built_in">LinkedList</span>&lt;<span class="type">String</span>&gt;();</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i != values.length; i++)&#123;</span><br><span class="line">        queue.<span class="built_in">add</span>(values[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">reconPreOrder</span>(queue);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="type">static</span> Node <span class="title">reconPreOrder</span><span class="params">(Queue&lt;<span class="type">String</span>&gt; queue)</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="type">String</span> value = queue.<span class="built_in">poll</span>();</span><br><span class="line">    <span class="keyword">if</span>(value.<span class="built_in">equals</span>(<span class="string">&quot;#&quot;</span>))&#123;</span><br><span class="line">        <span class="keyword">return</span> null;</span><br><span class="line">    &#125;</span><br><span class="line">    Node head  = <span class="keyword">new</span> <span class="built_in">Node</span>(Integer.<span class="built_in">valueOf</span>(value));</span><br><span class="line"></span><br><span class="line">    head.left = <span class="built_in">reconPreOrder</span>(queue);</span><br><span class="line">    head.right = <span class="built_in">reconPreOrder</span>(queue);</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="微软原题"><a href="#微软原题" class="headerlink" title="微软原题"></a><strong>微软原题</strong></h2><p>请把一张纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。</p>
<p>此时折痕是凹下去的，即折痕突起的方式指向纸条的背面。</p>
<p>如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕、上折痕。</p>
<p>给定一个输入参数N，代表纸条都从下边向上方连续对折N次。</p>
<p>请从上到下打印所有折痕的方向。</p>
<p>分析:通过实际操作得出，第一次的折痕是凹折痕，第二次对折后，在第一次对折的上方的折痕是凹折痕，下方是凸折痕。分别记为凹2和凸2。继续对折，会在凹2的上方出现凹折痕，在下方出现凸折痕；会在凸2的上方出现凹折痕，凸2的下方出现凸折痕。</p>
<p>由此可以得出:此规律可以写成一个二叉树，根节点为第一次对折出来的折痕。左子树为凹折痕，右子树为凸折痕。其子树也具有这样的规律</p>
<figure class="highlight reasonml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">public static void print<span class="constructor">AllFolds(<span class="params">int</span> N)</span>&#123;</span><br><span class="line">    <span class="comment">//1 ，true 代表第一个节点，且为凹</span></span><br><span class="line">    print<span class="constructor">Process(1,N,<span class="params">true</span>)</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//递归过程中，来到了某一个节点</span></span><br><span class="line"><span class="comment">//i是节点的层数，N一共的层数，down == true 凹 ， down == false 凸</span></span><br><span class="line">public static void print<span class="constructor">Process(<span class="params">int</span> <span class="params">i</span>,<span class="params">int</span> N,<span class="params">boolean</span> <span class="params">down</span>)</span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(i &gt; N)&#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    print<span class="constructor">Process(<span class="params">i</span>+1,N,<span class="params">true</span>)</span>;</span><br><span class="line">    <span class="module-access"><span class="module"><span class="identifier">System</span>.</span></span>out.println(down ? <span class="string">&quot;凹&quot;</span> : <span class="string">&quot;凸&quot;</span>);</span><br><span class="line">    print<span class="constructor">Process(<span class="params">i</span>+1,N,<span class="params">false</span>)</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/wang-cheng/tags/%E5%B7%A6%E7%A5%9E/" rel="tag"># 左神</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/03/26/%E7%AE%97%E6%B3%95%E4%B8%93%E9%A2%98/" rel="prev" title="算法专题">
      <i class="fa fa-chevron-left"></i> 算法专题
    </a></div>
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/04/01/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E4%BA%8C/" rel="next" title="算法笔记(二)">
      算法笔记(二) <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80"><span class="nav-number">1.</span> <span class="nav-text">算法基础</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F%E5%92%8C%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F-O-N"><span class="nav-number">1.1.</span> <span class="nav-text">计数排序和基数排序 O(N)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%9F%BA%E4%BA%8E%E6%AF%94%E8%BE%83%E7%9A%84%E7%AE%97%E6%B3%95%E5%92%8C%E4%B8%8D%E5%9F%BA%E4%BA%8E%E6%AF%94%E8%BE%83%E7%9A%84%E7%AE%97%E6%B3%95"><span class="nav-number">1.2.</span> <span class="nav-text">基于比较的算法和不基于比较的算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%B8%AD%E5%B8%B8%E8%A7%81%E7%9A%84%E5%9D%91"><span class="nav-number">1.3.</span> <span class="nav-text">排序算法中常见的坑</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%AE%97%E6%B3%95%E6%B1%87%E6%80%BB"><span class="nav-number">1.4.</span> <span class="nav-text">算法汇总</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E9%80%89%E6%8B%A9"><span class="nav-number">1.5.</span> <span class="nav-text">排序算法的选择</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B7%A5%E7%A8%8B%E4%B8%8A%E5%AF%B9%E6%8E%92%E5%BA%8F%E7%9A%84%E4%B8%80%E4%BA%9B%E6%94%B9%E8%BF%9B"><span class="nav-number">1.6.</span> <span class="nav-text">工程上对排序的一些改进</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%AF%94%E8%BE%83%E5%99%A8%E7%9A%84%E4%BD%BF%E7%94%A8"><span class="nav-number">1.7.</span> <span class="nav-text">比较器的使用</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%93%BE%E8%A1%A8"><span class="nav-number">1.8.</span> <span class="nav-text">链表</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%93%88%E5%B8%8C%E8%A1%A8"><span class="nav-number">1.8.1.</span> <span class="nav-text">哈希表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%9C%89%E5%BA%8F%E8%A1%A8"><span class="nav-number">1.8.2.</span> <span class="nav-text">有序表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E6%90%9C%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%88%A0%E9%99%A4"><span class="nav-number">1.8.3.</span> <span class="nav-text">搜索二叉树的删除</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%BA%A2%E9%BB%91%E6%A0%91"><span class="nav-number">1.8.4.</span> <span class="nav-text">红黑树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%93%BE%E8%A1%A8%E8%A7%A3%E9%A2%98%E7%9A%84%E6%96%B9%E6%B3%95%E8%AE%BA"><span class="nav-number">1.8.5.</span> <span class="nav-text">链表解题的方法论</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">1.9.</span> <span class="nav-text">二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E9%9D%9E%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">1.9.1.</span> <span class="nav-text">非递归遍历二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A6%82%E4%BD%95%E5%88%A4%E6%96%AD%E4%B8%80%E6%A3%B5%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E6%98%AF%E6%90%9C%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">1.9.2.</span> <span class="nav-text">如何判断一棵二叉树是否是搜索二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A6%82%E4%BD%95%E5%88%A4%E6%96%AD%E4%B8%80%E6%A3%B5%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">1.9.3.</span> <span class="nav-text">如何判断一棵二叉树是完全二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A6%82%E4%BD%95%E5%88%A4%E6%96%AD%E4%B8%80%E6%A3%B5%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E6%98%AF%E6%BB%A1%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="nav-number">1.9.4.</span> <span class="nav-text">如何判断一棵二叉树是否是满二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%A6%82%E4%BD%95%E5%88%A4%E6%96%AD%E4%B8%80%E6%A3%B5%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E6%98%AF%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91-%E4%BA%8C%E5%8F%89%E6%A0%91%E9%A2%98%E7%9B%AE%E5%A5%97%E8%B7%AF"><span class="nav-number">1.9.5.</span> <span class="nav-text">如何判断一棵二叉树是否是平衡二叉树(二叉树题目套路)</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%89%9B%E5%AE%A2NC102%E9%A2%98%E7%9B%AE"><span class="nav-number">1.10.</span> <span class="nav-text">牛客NC102题目</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%9C%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E6%89%BE%E5%88%B0%E4%B8%80%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E5%90%8E%E7%BB%A7%E8%8A%82%E7%82%B9"><span class="nav-number">1.11.</span> <span class="nav-text">在二叉树中找到一个节点的后继节点</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%BA%8F%E5%88%97%E5%8C%96%E5%92%8C%E5%8F%8D%E5%BA%8F%E5%88%97%E5%8C%96"><span class="nav-number">1.12.</span> <span class="nav-text">字符串的序列化和反序列化</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%BE%AE%E8%BD%AF%E5%8E%9F%E9%A2%98"><span class="nav-number">1.13.</span> <span class="nav-text">微软原题</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">王诚</p>
  <div class="site-description" itemprop="description">命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/wang-cheng/archives/">
        
          <span class="site-state-item-count">32</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/wang-cheng/tags/">
          
        <span class="site-state-item-count">12</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">王诚</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/wang-cheng/lib/anime.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.ui.min.js"></script>

<script src="/wang-cheng/js/utils.js"></script>

<script src="/wang-cheng/js/motion.js"></script>


<script src="/wang-cheng/js/schemes/pisces.js"></script>


<script src="/wang-cheng/js/next-boot.js"></script>




  















  

  

  

</body>
</html>
